The invention relates to a variable word length code decoding method and apparatus for decoding an input variable word length code sequence, and more particularly relates to a decoding method which decodes the input variable word length code sequence quickly by using relatively small capacity code tables.
As is well known in the art, an amount of data to be transmitted or to be stored can be reduced by using a variable word length coding technique. In this technique, a variable word length code set is determined based on a generation probability distribution of symbols to be outputted from an information source. More specifically, shorter length codes are assigned to symbols with higher generation probabilities while longer length codes are assigned to symbols with lower generation probabilities. Thus, the amount of data can be reduced.
Three conventional methods are known for decoding the input variable word length code sequence.
The first conventional method uses a single code table which stores a binary code tree representing a variable word length code set. In the method, a variable word length code which coincides with a part of the input variable word length code sequence is searched by tracing the binary code tree on a bit-by-bit basis.
The second conventional method uses another type of code table which stores bit patterns of variable word length codes and the corresponding decoded values. In that method, each variable word length code stored in the code table is compared with the input variable word length code sequence on a code-by-code basis.
The third conventional method uses still another type of code table having addresses that represent data associated with bit patterns of variable word length codes and which stores a decoded value and a code length in the corresponding address. In that table, the required number of address bits corresponds to the maximum code length in a variable word length code set. The third conventional method is described, for example, in U.S. Pat. No. 4,509,038.
However, the conventional methods have the following disadvantages. The first conventional method requires a long decoding time because the method performs bit-by-bit operations. The second conventional method also requires a long decoding time because each code in the table is compared code-by-code with the input sequence. The third method, on the other hand, requires a huge capacity memory though the method requires a short decoding time.